从参数空间到函数空间理解GBDT+XGBoost

您所在的位置：网站首页 › what is gbdt › 从参数空间到函数空间理解GBDT+XGBoost

从参数空间到函数空间理解GBDT+XGBoost

2022-12-16 07:46| 来源: 网络整理| 查看: 265

内容摘要泰勒公式最优化方法梯度下降法牛顿法从参数空间到函数空间从Gradient descend到Gradient boosting 从Newton's method到Newton Boosting Gradient boosting tree算法原理 Newton Boosting算法原理 LightGBM 泰勒公式定义：是一个用函数在某点的信息，描述其附近取值的公式。

基本形式：

其中一阶泰勒展开式就是求一阶导，二阶展开式即求二阶导。x0为已知，公式表示f(x)在x0附近的展开。

GDBT或是xgb都是一个参数迭代的过程，因此这里表示一个迭代形式的泰勒函数：

假设将f(x^t) 在x^(t-1)处进行展开：梯度下降法（Gradient Descend Method）

机器学习中需要最小化损失函数L(θ),这个θ就是要求解的模型参数。GDM常用于求解无约束最优化问题，是一种迭代方法。初始话θ为θ^0，不断迭代来更新θ的值，进行损失函数的极小化。

迭代公式 θ^t = θ^(t-1)+△θ 进行一阶泰勒展开：

要使得L(θ^t) < L(θ^(t-1)),则可取：

其中解释一下为何△θ要取值为上式：首先明确，a的值为正，为了保证△θ恒为负数，则需要乘上L’(θ^t-1)先保证其为整数，再加上负号即可。其实a就是我们常用的学习速率 a如何选取？对于这个问题其实有很多方法可以使用，如果考虑使用full gradient较为笨但是精确的方法是line search，但是其复杂度过高，因此通常我们选取一个很小的值即可例如0.01-0.1之间。牛顿法

牛顿法就是求取二阶泰勒展开：

假设我们要求的参数θ是一维，则记一阶导数为g，二阶导数为h，那么上式可表示为：

此时若求取L(θ^t) 的极小值，则令g△θ+h△θ^2/2极小，求取其一阶导数为0时的△θ即可：

如果参数θ是向量形式，那么可以向高维空间推广，此时的h为H（海森矩阵）。

以上介绍的梯度下降和牛顿法均为参数空间的优化算法如何从参数空间推广到函数空间呢？即从Gradient descend到Gradient boosting；从Newton's method到Newton Boosting 下面介绍GBDT和xgb中使用的函数空间的优化算法，其基本原理还是梯度下降和牛顿法。关系是这样的： GBDT泛指一切梯度提升树，包括XGB。为了区分二者，可以利用其梯度下降的原理进行区分：

GBDT在函数空间中利用梯度下降进行优化 XGB在函数空间利用牛顿法进行优化

1. 梯度下降从参数空间到函数空间

其中对于函数空间，仅仅是将参数的拟合换为函数的拟合，每次仍然迭代的是一个负梯度，只是其最终得到的是增量函数的累加而不是增量参数累加。 GBDT里，迭代项ft(x)就是我们的决策树，最终将每棵决策树的预测值（函数）加起来。

2. 牛顿法从参数空间到函数空间

对于牛顿法的函数空间优化，其方法类似于梯度下降的函数空间优化

3. boosting算法小结无论是梯度下降还是牛顿法，其函数空间上的boosting优化模型都看作是一类加法模型，相加的对象可以是一系列弱分类器或是回归树。

4. 牛顿法小结牛顿法是梯度下降的进一步优化，梯度下降利用目标函数的一阶偏导信息，以负梯度方向作为搜索方向，只考虑目标函数在迭代点的局部性质；而牛顿法不仅使用目标函数的一阶偏导数，还进一步利用了目标函数的二阶偏导，这样就考虑了梯度变化的趋势，因而能更全面地确定合适的搜索方向以加快收敛。

GBDT原理分析

GBDT最早由Friedman提出，其核心是拟合前面迭代所留下来的残差，使其达到最小。

模型F定义为一个加法模型：

其中x为输入样本，h为分类回归树，w是分类回归树的参数，a是每棵树的权重。

通过最小化损失函数求解最优模型：

GBDT原是论文的算法伪代码：

算法的输入(xi,yi)分别是样本和lable，T为样本个数，L为损失函数

GBDT的学习过程是使得前面拟合的残差达到最小，那么首先计算残差，即算法中的2.1步，也称为响应。接着学习第t棵树时就是寻找最新的残差的最小值。可以看到lable yi变成了前t-1棵树的残差值。然后寻找合适的步长（通常情况，不使用line search，而是手动给一个很小的值）最后将第t棵树与前t-1棵树加起来，更新模型即可。

XGBoost原理

模型的函数形式

xgb同样是一个加性模型，同样是在学习多棵树的结果并将其累加。f(x)就是每一棵树。其中q(x)表示将样本x分到了某个叶子节点上，w是叶子节点的分数，所以wq(x)就表示回归树对样本的预测值。

回归树的预测输出是一个实数的分数，因此可以用于回归和分类，以及排序等任务。目标函数

首先回忆一下参数空间的目标函数：

实际上就是一个误差函数+正则化项

其中误差函数可以是平方误差或是对数误差等；正则化项可以是L1或L2

正则化项

wepon大神说道，正则化项的理解可以从贝叶斯先验角度去理解。也就是说，如果引入L2，那么就是假设模型参数服从正态分布（相当于对参数加上了分布约束），这样一来就将参数的取值进行一定的限制，同时可以知道，正态分布取0附近的概率最大，因此又将参数空间可能的范围进一步缩小，模型最终学习出来的参数取值都在0附近。

现在来看函数空间的目标函数

其中正则化项是对每一棵树的复杂度进行惩罚。相比于GBDT，xgb目标函数就是多了一个正则化项。这样的做法使得模型不易过拟合。既然是对复杂度做惩罚，那么树的什么特性可以反映复杂度？

树的深度、内部节点个数、叶子节点个数，叶节点分数 xgb中选用了叶子节点个数(T)，叶节点分数(w)来反映树的复杂度，其复杂度定义如下：

看完正则化项后再来关心一下目标函数中的误差函数

首先模型第t次迭代后将ft(x)与前t次的迭代结果进行相加，并代入目标函数，即式2，然后将误差项在yt-1处进行二阶展开，然后去掉常数项得到：

上面这个形式跟牛顿法的形式几乎一样，由于f在函数空间中是一个树的形式，则将f写为树的结构：代入目标函数中得到：

虽然现在loss函数可以求最小值了，但是公式的两项并不统一，即：如何将两项进行统一以方便求导呢？因为样本都会落在每一个节点上面，因此可以定义如下：对每一个样本都相应有一个gi和hi。从最终的公式可以看到，由于是按照叶子节点进行累加，所以相当于每一个叶子节点均有一个误差函数，都要进行相应的误差计算。根据转换后的损失函数，就可以求极小值了，前提是树结构确定：相当于每一棵树的最小损失都可以计算了。

既然前提是需要树结构确定，那么如何确定树的结构？即如何确定树节点的分裂方法？

可以暴力枚举全部的树结构然后选择损失最小的结构即可。明显是一个NP问题。不现实！

贪心法：每次尝试分裂一个叶节点，计算前后增益，选择增益最大的保留。

那么增益如何计算？ xgb增益计算方法的演进：

初始版本：

这样的方法相当于去遍历所有可能分割的分割点，然后计算增益，最后选取最大的增益的分列方式去分割，明显负责度太高！！

近似算法：对于每一个特征，只考虑分位点，以减少复杂度，分位点的选取粒度有两种：全局global和局部local。全局速度快但是经度降低。解释一下：先将某特征的特征值从小到大排序，再选取分位点进行计算增益即可。 3. xgb中采用的树节点分裂方法（增益计算）如何看权重分位点的选取呢？上图中前六个特征值的权重之和为0.6，7-8的权重和为0.6，最后一个为0.6，就这选取权重之和相同的点来进行分位点的选取，然后再计算增益。

内容参考wepon大神天池直播

【本文地址】

从参数空间到函数空间理解GBDT+XGBoost

从参数空间到函数空间理解GBDT+XGBoost

今日新闻

推荐新闻